#
# @lc app=leetcode.cn id=131 lang=python3
#
# [131] 分割回文串
#
# https://leetcode-cn.com/problems/palindrome-partitioning/description/
#
# algorithms
# Medium (72.49%)
# Likes:    983
# Dislikes: 0
# Total Accepted:    159.5K
# Total Submissions: 219.8K
# Testcase Example:  '"aab"'
#
# 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
# 
# 回文串 是正着读和反着读都一样的字符串。
# 
# 
# 
# 示例 1：
# 
# 
# 输入：s = "aab"
# 输出：[["a","a","b"],["aa","b"]]
# 
# 
# 示例 2：
# 
# 
# 输入：s = "a"
# 输出：[["a"]]
# 
# 
# 
# 
# 提示：
# 
# 
# 1 
# s 仅由小写英文字母组成
# 
# 
#
# %%
from typing import List
# @lc code=start
class Solution:
    class TreeNode:
        def __init__(self, val='0'):
            self.val = val
            self.children = []
    # construct tree
    def func(self, s, root):
        if s:
            # not None
            for step in range(len(s)):
                if s[0:step+1] == s[0:step+1][::-1]:
                    newnode = self.TreeNode(s[0:step+1])
                    root.children.append(newnode)
                    self.func(s[step+1:], newnode)
    # post visit tree
    def post_visit(self, root):
        tree_stack = [root]
        visited_flag = {}
        is_true_leafe = False
        all_path = []
        while tree_stack:
            # not None
            current = tree_stack[-1]
            while current.children:
                # not None
                not_visited_children = [child for child in current.children if not visited_flag.get(child, False)]
                if not_visited_children:
                    # not None
                    # put into the stack
                    tree_stack.append(not_visited_children[0])
                    current = not_visited_children[0]
                    is_true_leafe = True
                else:
                    is_true_leafe = False
                    break
            # 两种情况
            if is_true_leafe:
                # 添加路径
                all_path.append([node.val for node in tree_stack])
            # 节点设置为访问并弹出
            visited_flag[tree_stack.pop()] = True
        # pass
        # 过滤所有是回文子串的要求是，每一个path都是回文子串
        return [path[1:] for path in all_path]
    def partition(self, s: str) -> List[List[str]]:
        treerootnode = self.TreeNode()
        self.func(s, treerootnode)
        return self.post_visit(treerootnode)
# @lc code=end
solution = Solution()
print(solution.partition("aab"))
